#ifndef LIBACCENT_ALGORITHMS_FILTER_HPP
#define LIBACCENT_ALGORITHMS_FILTER_HPP

#include "accent/core.hpp"
#include "accent/utility/safe_position.hpp"
#include "accent/utility/tag_functions.hpp"

namespace accent
{
  namespace detail
  {
    template <typename Range, typename Predicate>
    class filtered
    {
      Range wrapped;
      Predicate p;

      void next() {
        while (!wrapped.empty() && !p(wrapped.front()))
          wrapped.pop_front();
      }
      void prev() {
        while (!wrapped.empty() && !p(wrapped.back()))
          wrapped.pop_back();
      }

    public:
      using traversal = support::minimum_tag<typename Range::traversal,
                                             bidirectional_traversal_tag>;

      filtered(Range r, Predicate p) : wrapped(r), p(p) { next(); prev(); }

      bool empty() const { return wrapped.empty(); }
      void pop_front() { wrapped.pop_front(); next(); }
      auto front() const -> decltype(wrapped.front()) { return wrapped.front();}

      // FIXME: assuming stateless predicate here
      typedef support::safe_position<Range> position;

      position front_position() const { return wrapped.front_position(); }
      filtered from(position n) const { return { wrapped.from(n), p }; }
      filtered until(position n) const { return { wrapped.until(n), p }; }

      position back_position() const { return wrapped.back_position(); }
      auto back() const -> decltype(wrapped.front()) { return wrapped.back(); }
      void pop_back() { wrapped.pop_back(); prev(); }
    };
  }

  template <typename Range, typename Predicate>
  detail::filtered<Range, Predicate> filter(Range r, Predicate p)
  {
    return { r, p };
  }

}

#endif
